The present invention relates to cryptographic methods and, more particularly, to a method for signing and encrypting messages using keys with different moduli.
Encryption is the process of disguising intelligible information, called plaintext, to hide its substance from eavesdroppers. Encrypting plaintext produces unintelligible data called ciphertext. Decryption is the process of converting ciphertext back to its original plaintext. Using encryption and decryption, two parties can send messages over an insecure channel without revealing the substance of the message to eavesdroppers.
A cryptographic algorithm or cipher is a mathematical function used in the encryption and decryption of data. Many cryptographic algorithms work in combination with a key to encrypt and decrypt messages. The key, typically a large random number, controls the encryption of data by the cryptographic algorithm. The same plaintext encrypts to different ciphertext with different keys. In general, it is extremely difficult to recover the plaintext of a message without access to the key, even by an eavesdropper having full knowledge of the cryptographic algorithm.
One type of cryptographic algorithm, known as public key algorithms, use different keys for encryption and decryption. An encryption key, also called the public key, is used for encrypting data and is accessible to other users. Anyone can use the public key to encrypt messages. A decryption key, also called the private key, is kept secret and is used to decrypt messages. Only a person with the private key can decrypt messages encrypted with the corresponding public key. During use, the sender encrypts a message using the public key of the intended recipient. Only the intended recipient can decipher the message using his private key. Since the private key is not distributed, public key algorithms avoid the problems of key exchange inherent in symmetric algorithms.
One of the most popular public key algorithms is the RSA algorithm, named after its three inventors—Ron Rivest, Adi Shamir, and Leonard Adleman. The RSA algorithm takes a message M and encrypts it using the formula C=ME mod N, where N is the product of two large prime numbers P, Q chosen at random. The exponent E is a number relatively prime to (P-1)(Q-1). The encrypted message C is deciphered using the formula M=CD mod N where D=E−1 mod ((p−1)(q−1)). The exponent E and modulus N are used as the public key. The exponent D is the private key. The primes P and Q are not needed once the public and private keys have been computed but should remain secret.
The RSA algorithm, and other public key algorithms, allow secure communications between two parties, but do not provide a means for authenticating the parties. When a person receives a message encrypted with his public key, he can be assured that the content of the encrypted message is secret, since only he possesses the key for decrypting the message. However, the party receiving the encrypted message has no assurance of the identity of the sending party, since anyone with his public key could have encrypted the message.
If the receiving party desires to authenticate the sending party's identity, the sending party may sign the message by encrypting it with his private key. The receiving party can then use the sender's public key to decrypt the message. If the message is decrypted successfully, only the sending party in possession of the private key could have sent that message. This process of authenticating the message by encryption using the sender's private key is referred to as signing.
It is known to doubly encrypt messages to provide both secure communications and authentication capability. In this case, each party to the communication possesses a public key used for encrypting messages and a private key used for decrypting messages. Assume that party A wishes to send party B a message. Party A encrypts the message first, using party A's private key. The resulting ciphertext is encrypted a second time, using party B's public key. The result of these second encryption operations is transmitted to party B. Party B decrypts the message using party B's private key. Since party B is the only person in possession of the private key, only he can decrypt the message, so the communication is secure. The result of the first decryption operation is the inner ciphertext produced by encrypting the original message with party A's private key. Thus, party B can then use party A's public key to decrypt the inner ciphertext to obtain the original message. Since only party A possesses the private key that can generate the inner ciphertext, party A's identity is authenticated to party B.
When using the RSA algorithm for encryption, the message M is broken into blocks such that the length of each message block is less than the encryption modulus. The reason for breaking the message into blocks having a length less than the encryption modulus is to avoid loss of data. A similar procedure is typically used when a message is to be signed using the sender's private key and then encrypted using the recipient's public key. In this case, the message M is partitioned into blocks of a fixed length one or more bits less than the binary length of a first encryption modulus, which is used in the signing operation. The output of the signing operation is a sequence of blocks equal to the length of the first encryption modulus. The blocks output during the signing operation are recombined and repartitioned to form input blocks of a fixed length one or more bits less than the length of a second encryption modulus associated with the receipient's public key. The resulting message blocks are then encrypted using the recipient's public key. This procedure avoids loss of data by ensuring that the numerical value of each message block is less than the encryption modulus used during the signing or encryption operations.